#!/usr/bin/env python
# coding: utf-8

from __future__ import division, print_function, unicode_literals


class Node:
    """
    blah
    """

    def __init__(self):
        self.d = { 0: None, 1: None }
        self.frq = 0
        self.ch = None
        self.is_leaf = True


def f(startsize, step):
    q1 = []
    q2 = []

    frq = [next(step) for i in range(26)]
    alphabet = [chr(i + ord('a')) for i in range(26)]

    i = 0
    while i < 26:
        n = Node()
        n.frq = frq[i]
        n.ch = alphabet[i]
        q1.append(n)
        i += 1
    q1.sort(key=lambda x: (x.frq, x.ch))
    m = [None] * 2
    while len(q1) + len(q2) > 1:
        for i in range(2):
            if len(q1) == 0:
                m[i] = q2.pop(0)
            elif len(q2) == 0:
                m[i] = q1.pop(0)
            elif q1[0].frq < q2[0].frq:
                m[i] = q1.pop(0)
            else:
                m[i] = q2.pop(0)

        n = Node()
        n.d[0] = m[0]
        n.d[1] = m[1]
        n.is_leaf = False
        n.frq = n.d[0].frq + n.d[1].frq
        q2.append(n)

    assert len(q2) == 1 and len(q1) == 0 or \
        len(q1) == 1 and len(q2) == 0

    print_huffman_tree(q2[0] if len(q2) == 1 else q1[0])


def print_huffman_tree(root, acc_str=''):
    if root.ch or root.is_leaf:
        print('{0:<4s} {1:<30s} ({2:d})'.format(root.ch, acc_str, root.frq))
    if root.d[0]:
        print_huffman_tree(root.d[0], acc_str=acc_str + '0')
    if root.d[1]:
        print_huffman_tree(root.d[1], acc_str=acc_str + '1')

def minseq(start, step=0):
    print('minseq: {}'.format(start))
    yield start
    print('minseq: {}'.format(start + step))
    yield start + step
    this = start + step * 2 + 1
    prev = start + step
    acc = start
    while True:
        print('minseq: {}'.format(this))
        yield this
        (this, prev, acc) = (acc + prev + 1, this, acc + prev)


if __name__ == '__main__':
    # f(1, (1 for i in range(26)))
    # print()
    # f(1, (i for i in range(26)))
    # print()
    # f(1, (2 * i for i in range(26)))
    # print()
    # f(1, (2 ** i + 1 for i in range(26)))
    # print()
    # f(1, (2 ** (i + 1) - 2 ** i for i in range(26)))
    # print()
    # f(1, (2 ** (i + 1) - 2 ** i - i for i in range(26)))
    # print()
    # f(64, iter(lambda: 1, 0))
    # print('\n' + '=' * 80 + '\n')
    f(1, minseq(1))
